package solutions.leetcode.easy

import java.util.PriorityQueue
import kotlin.math.max

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/take-gifts-from-the-richest-pile/">2558. 从数量最多的堆取走礼物</a>
 */
private class Solution2558 {
    fun pickGifts(gifts: IntArray, k: Int): Long {
        val q = PriorityQueue<Int> {o1, o2 -> o2 - o1}
        var sum = 0L
        for (item in gifts) {
            q.offer(item)
            sum += item
        }
        var t = k
        while (t-- > 0) {
            val max = q.poll()
            if (max == 1) {
                return sum
            }
            val sub = Math.sqrt(max.toDouble()).toInt()
            q.offer(sub)
            sum -= (max - sub)
        }
        return sum
    }
}

fun main() {
    
}